//==============================================================================
// Copyright (c) 2008-2013 Niall Ryan. All Rights Reserved.
//==============================================================================

#ifndef HYDRA_QUEUES_LOCKFREESTAMPEDQUEUE_H
#define HYDRA_QUEUES_LOCKFREESTAMPEDQUEUE_H 1

#include "hydra/allocators/BasicAllocator.h"
#include "hydra/atomic/AtomicPair.h"

namespace Hydra
{
	/**
	 * A lock free queue which uses stamped references to avoid the ABA problem.
	 */
	template<typename T, typename Allocator=BasicAllocator>
	class LockFreeStampedQueue
	{
		struct Node
		{
			T m_item;
			AtomicPair<Node*, unsigned int> m_next;
		};

	public:
		LockFreeStampedQueue()
		{
			Node* sentinel = allocNode();
			sentinel->m_next.set(NULL, 0);
			m_alloc.m_head.set(sentinel, 0);
			m_tail.set(sentinel, 0);
		}

		~LockFreeStampedQueue()
		{
			//free all nodes
			Node* node = m_alloc.m_head.getFirst();
			while( node )
			{
				Node* nextNode = node->m_next.getFirst();
				freeNode(node);
				node = nextNode;
			}
		}

		void push(const T& item)
		{
			Node* node = allocNode();
			node->m_item = item;
			node->m_next.set(NULL, 0);
			while( true )
			{
				Node* last;
				Node* next;
				unsigned int lastStamp, nextStamp;
				m_tail.get(&last, &lastStamp);
				last->m_next.get(&next, &nextStamp);
				//make sure the last node is still the tail node. Otherwise it may have already been freed and
				// the next pointer would be garbage
				if( last == m_tail.getFirst() ) //TODO: should check stamp too i think
				{
					//check if the tail was actually the tail
					if( next == NULL )
					{
						if( last->m_next.compareAndSwap(node, nextStamp+1, next, nextStamp) )
						{
							m_tail.compareAndSwap(node, lastStamp+1, last, lastStamp);
							return;
						}
					}
					else
					{
						m_tail.compareAndSwap(next, lastStamp+1, last, lastStamp);
					}
				}
			}
		}

		bool pop(T& item)
		{
			while( true )
			{
				Node* first;
				Node* last;
				Node* next;
				unsigned int firstStamp, lastStamp, nextStamp;
				m_alloc.m_head.get(&first, &firstStamp);
				m_tail.get(&last, &lastStamp);
				first->m_next.get(&next, &nextStamp);
				//ensure that first is still the head node. Otherwise the head may have been already freed, and the
				// next pointer would have been read from deallocated memory, leading to a possible crash when we
				// dereference it.
				if( first == m_alloc.m_head.getFirst() )
				{
					//head and tail pointing to the same node, queue might be empty
					if( first == last )
					{
						//no next node means we had only the head node when we go the next pointer, queue was therefore
						// empty
						if( next == NULL )
							return false;
						//tail was not pointing to the actual tail, attempt to give it a hand
						m_tail.compareAndSwap(next, lastStamp+1, last, lastStamp);
					}
					else
					{
						//read the item from the node, this must be done before the compareAndSwap, otherwise another
						// thread could free the node between the compareAndSwap and the read. Also note that we may
						// be reading from deallocated memory here, but that's ok as then the following compareAndSwap
						// will fail.
						item = next->m_item;
						//attempt to move the head
						if( m_alloc.m_head.compareAndSwap(next, firstStamp+1, first, firstStamp) )
						{
							//freeing the popped node, other threads may be left with a pointer to deallocated memory or
							// a recycled node, but the stamps ensure they will not use it.
							freeNode(first);
							return true;
						}
					}
				}
			}
		}

	private:
		Node* allocNode()
		{
			Node* node = reinterpret_cast<Node*>(m_alloc.alloc(sizeof(Node)));
			new(node) Node;
			return node;
		}
		void releaseNode(Node* node)
		{
			node->~Node();
			m_alloc.release(node);
		}
		void freeNode(Node* node)
		{
			node->~Node();
			m_alloc.free(node);
		}

		struct AllocAndHead : public Allocator
		{
			AtomicPair<Node*, unsigned int> m_head;
		};
		AllocAndHead m_alloc;
		AtomicPair<Node*, unsigned int> m_tail;
	};
}

#endif
